package algorithm_demo.demo02;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 序列化和反序列化二叉树
 *
 * @author Api
 * @date 2023/2/11 9:45
 */
public class Code03_SerialTree {
    public static class TreeNode {
        public int value;
        public TreeNode left;
        public TreeNode right;

        public TreeNode() {

        }

        public TreeNode(int value) {
            this.value = value;
        }
    }

    //先序序列化
    public static Queue<String> preSerial(TreeNode head) {
        Queue<String> ans = new LinkedList<>();
        pres(head, ans);
        return ans;
    }

    public static void pres(TreeNode head, Queue<String> ans) {
        if (head == null) {
            ans.add(null);
        } else {
            ans.add(String.valueOf(head.value));
            pres(head.left, ans);
            pres(head.right, ans);
        }
    }

    //根据先序队列，反序列化二叉树
    public static TreeNode buildByPreQueue(Queue<String> preList) {
        if (preList == null || preList.size() == 0) {
            return null;
        }
        return preb(preList);
    }

    public static TreeNode preb(Queue<String> preList) {
        String value = preList.poll();
        if (value == null) {
            return null;
        }
        TreeNode x = new TreeNode(Integer.parseInt(value));
        x.left = preb(preList);
        x.right = preb(preList);
        return x;
    }

    //二叉树按层序列化
    public static Queue<String> levelSerial(TreeNode head) {
        Queue<String> ans = new LinkedList<>();
        if (head == null) {
            ans.add(null);
        } else {
            ans.add(String.valueOf(head.value));
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            queue.add(head);
            while (!queue.isEmpty()) {
                head = queue.poll();
                if (head.left != null) {
                    ans.add(String.valueOf(head.left.value));
                    queue.add(head.left);
                } else {
                    ans.add(null);
                }
                if (head.right != null) {
                    ans.add(String.valueOf(head.right.value));
                    queue.add(head.right);
                } else {
                    ans.add(null);
                }
            }
        }
        return ans;
    }

    //队列按层反序列化出二叉树
    public static TreeNode buildByLevelQueue(Queue<String> levelList) {
        if (levelList == null || levelList.size() == 0) {
            return null;
        }
        TreeNode head = generateNode(levelList.poll());
        Queue<TreeNode> queue = new LinkedList<>();
        if (head != null) {
            queue.add(head);
        }
        TreeNode treeNode = null;
        while (!queue.isEmpty()) {
            treeNode = queue.poll();
            treeNode.left = generateNode(levelList.poll());
            treeNode.right = generateNode(levelList.poll());
            if (treeNode.left != null) {
                queue.add(treeNode.left);
            }
            if (treeNode.right != null) {
                queue.add(treeNode.right);
            }
        }
        return head;
    }

    //这里返回的是字符串
    public String serialize(TreeNode root) {
        Queue<String> ans = new LinkedList<String>();
        pres(root, ans);
        StringBuilder sb = new StringBuilder();
        while (!ans.isEmpty()) {
            sb.append(ans.poll()).append(",");
        }
        String value = sb.toString();
        return value.substring(0, value.length() - 2);
    }


    public static TreeNode generateNode(String val) {
        if (val == null) {
            return null;
        }
        return new TreeNode(Integer.parseInt(val));
    }
    //输入的是字符串
    public static TreeNode deserialize(String data) {
        Queue<String> ans = new LinkedList<>();
        if (data == null || data.length() == 0) {
            return null;
        }

        String[] split = data.split(",");
        for (String s : split) {
            ans.add(String.valueOf(s));
        }
        return preb1(ans);
    }
    public static TreeNode preb1(Queue<String> preList) {
        String value = preList.poll();
        if (value == null || "null".equals(value)) {
            return null;
        }
        TreeNode x = new TreeNode(Integer.parseInt(value));
        x.left = preb1(preList);
        x.right = preb1(preList);
        return x;
    }

    public static void main(String[] args) {
        String a = "1,2,3,null,null,4,5";
        deserialize(a);
    }
}
